Find all anagrams in a string

Time: O(N); Space: O(1); easy

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input: s = “cbaebabacd” p = “abc”

Output: [0, 6]

Explanation:

  • The substring with start index = 0 is “cba”, which is an anagram of “abc”.

  • The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2:

Input: s = “abab” p = “ab”

Output: [0, 1, 2]

Explanation:

  • The substring with start index = 0 is “ab”, which is an anagram of “ab”.

  • The substring with start index = 1 is “ba”, which is an anagram of “ab”.

  • The substring with start index = 2 is “ab”, which is an anagram of “ab”.

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        result = []

        cnts = [0] * 26
        for c in p:
            cnts[ord(c) - ord('a')] += 1

        left, right = 0, 0

        while right < len(s):
            cnts[ord(s[right]) - ord('a')] -= 1

            while left <= right and cnts[ord(s[right]) - ord('a')] < 0:
                cnts[ord(s[left]) - ord('a')] += 1
                left += 1

            if right - left + 1 == len(p):
                result.append(left)
            right += 1

        return result

[2]:

sol = Solution1()

s = "cbaebabacd"
p = "abc"
assert sol.findAnagrams(s, p) ==  [0, 6]

s = "abab"
p = "ab"
assert sol.findAnagrams(s, p) == [0, 1, 2]